#pragma once
#include <iostream>

namespace key_bstree
{

template<class K>
struct bstree_node
{
    bstree_node<K>(K key = K())
        : _left(nullptr), _right(nullptr), _key(key)
    {}

    bstree_node<K>* _left;
    bstree_node<K>* _right;
    K _key;
};

template<class K>
class bstree
{
public:
    typedef bstree_node<K> node;

    bstree<K>()
    {}

    node* copy(node* root)
    {
        if (root == nullptr)
            return nullptr;

        node* new_root = new node(root->_key);
        new_root->_left = copy(root->_left);
        new_root->_right = copy(root->_right);

        return new_root;
    }

    bstree<K>(const bstree<K>& t)
    {
        _root = copy(t._root);
    }

    bstree<K>& operator=(bstree<K> t)
    {
        std::swap(_root, t._root);
    }

    void destroy(node* root)
    {
        if (root == nullptr)
            return;

        destroy(root->_left);
        destroy(root->_right);
        delete root;
    }

    ~bstree<K>()
    {
        destroy(_root);
        _root = nullptr;
    }


public:
    bool insert(const K& key)
    {
        if (_root == nullptr)
        {
            _root = new node(key);
            return true;
        }

        node* cur = _root;
        node* parent = nullptr;

        while (cur)
        {
            if (key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return false;
            }
        }

        if (key < parent->_key)
        {
            parent->_left = new node(key);
        }
        else
        {
            parent->_right = new node(key);
        }

        return true;
    }

    void inorder()
    {
        _inorder(_root);
        std::cout << std::endl;
    }

    void _inorder(node* root)
    {
        if (root == nullptr)
            return;

        _inorder(root->_left);
        std::cout << root->_key << " ";
        _inorder(root->_right);
    }

    bool find(const K& key)
    {
        node* cur = _root;

        while (cur)
        {
            if (key < cur->_key)
            {
                cur = cur->_left;
            }
            else if (key > cur->_key)
            {
                cur = cur->_right;
            }
            else
            {
                return true;
            }
        }

        return false;
    }

    bool erase(const K& key)
    {
        node* parent = nullptr;
        node* cur = _root;

        while (cur)
        {
            if (key < cur->_key)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                if (!cur->_left)
                {
                    if (parent == nullptr)
                        _root = _root->_right;
                    else if (cur == parent->_left)
                        parent->_left = cur->_right;
                    else
                        parent->_right = cur->_right;
                    delete cur;
                }
                else if (!cur->_right)
                {
                    if (parent == nullptr)
                        _root = _root->_left;
                    else if (cur == parent->_left)
                        parent->_left = cur->_left;
                    else
                        parent->_right = cur->_left;
                    delete cur;
                }
                else
                {
                    node* min_parent = cur;
                    node* min = cur->_right;

                    while (min->_left)
                    {
                        min_parent = min;
                        min = min->_left;
                    }

                    K minkey = min->_key;
                    erase(min->_key);
                    cur->_key = minkey;

                    // if (min == min_parent->_left)
                    //     min_parent->_left = min->_right;
                    // else
                    //     min_parent->_right = min->_right;
                    //
                    // cur->_key = min->_key;
                    //
                    // delete min;
                }
                return true;
            }
        }
        return false;
    }

// recursion
public:
    bool find_r(const K& key)
    {
        return _find_r(_root, key);
    }

    bool _find_r(node* root, const K& key)
    {
        if (root == nullptr)
            return false;

        if (key < root->_key)
            return _find_r(root->_left, key);
        else if (key > root->_key)
            return _find_r(root->_right, key);
        else
            return true;
    }

    bool insert_r(const K& key)
    {
        return _insert_r(_root, key);
    }

    bool _insert_r(node*& root, const K& key)
    {
        if (root == nullptr)
        {
            root = new node(key);
            return true;
        }

        if (key < root->_key)
            return _insert_r(root->_left, key);
        else if (key > root->_key)
            return _insert_r(root->_right, key);
        else
            return false;
    }

    bool erase_r(const K& key)
    {
        return _erase_r(_root, key);
    }

    bool _erase_r(node*& root, const K& key)
    {
        if (root == nullptr)
        {
            return false;
        }

        if (key < root->_key)
        {
            return _erase_r(root->_left, key);
        }
        else if (key > root->_key)
        {
            return _erase_r(root->_right, key);
        }
        else
        {
            node* del = root;
            if (!root->_left)
            {
                root = root->_right;
            }
            else if (!root->_right)
            {
                root = root->_left;
            }
            else
            {
                node* min = root->_right;
                while(min->_left)
                {
                    min = min->_left;
                }

                // min = min->_right; // ERR
                root->_key = min->_key;
                // return _erase_r(min, min->_key); // ERR
                return _erase_r(root->_right, min->_key);
            }

            delete del;
            return true;
        }
    }

private:
    node* _root = nullptr;
};

}